package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 103. 二叉树的锯齿形层序遍历
 * 
 * https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 * 
 * @author jie.deng
 *
 */
class Question0103Solution01 {

	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> retList = new ArrayList<>();
		if (root == null) {
			return retList;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		boolean reverse = false;
		while (!queue.isEmpty()) {
			int len = queue.size();
			List<Integer> list = new ArrayList<>(len);
			for (int i = 0; i < len; i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
			if (reverse) {
				Collections.reverse(list);
			}
			retList.add(list);
			reverse = !reverse;
		}

		return retList;
	}

}